#include <iostream>

// 定义单链表节点类，使用模板让节点可以存储任意类型的数据
template <typename T>
class Node {
public:
        // 存储节点的数据
        T data;
        Node<T>* next;
        // 构造函数，初始化节点的数据，并且将指向下一个节点的指针置为 nullptr
        Node(T value) : data(value) , next(nullptr) {}
};

// 定义单链表类，使用模板让链表可以存储任意类型的数据
template <typename T>
class LinkedList {
private:
        // 指向链表头节点的指针
        Node<T>* head;
        // 指向链表尾节点的指针
        Node<T>* tail;
        // 链表中节点的数量
        int size;

public:
        // 构造函数，初始化链表，将头指针和尾指针置为 nullptr，节点数量置为 0
        LinkedList() : head(nullptr) , tail(nullptr) , size(0) {}

        // 析构函数，用于释放链表中所有节点占用的内存
        ~LinkedList(){
            while(head != nullptr){
                Node<T>* temp = head;
                // 将头指针指向下一个节点
                head = head->next;
                delete temp;
            }
        }

        // 获取链表中节点的数量
        int GetSize() const {
            return size;
        }
        // 判断链表是否为空，即节点数量是否为 0
        bool IsEmpty() const {
            return size == 0;
        }

        // 在链表尾部添加一个新节点
        void append(T value) {
            // 创建一个新节点，存储传入的值
            Node<T>* NewNode = new Node<T>(value);

            if(IsEmpty()) {
                // 头指针和尾指针都指向新节点
                head = NewNode;
                tail = NewNode;
            }
            else {
                // 尾节点的 next 指针指向新节点
                tail->next = NewNode;
                // 尾指针指向新节点
                tail = NewNode;
            }
            size++;
        }

        // 在链表头部添加一个新节点
        void prepend(T value) {
            //创建新节点
            Node<T>* NewNode = new Node<T>(value);

            if(IsEmpty()) {
                // 头指针和尾指针都指向新节点
                head = NewNode;
                tail = NewNode;
            }
            else {
                NewNode->next = head;
                head = NewNode;
            }
            size++;
        }

        /* 
        @param index 索引
        @param value 插入值  
        */
        bool insert(int index,T value) {
            if(index < 0 || index > size) {
                return false;
            }

            // 若在头部插入，调用 prepend 方法
            if(index == 0) {
                prepend(value);
                return true;
            }
            //尾部插入
            if(index == size) {
                append(value);
                return true;
            }

            //创建新节点
            Node<T>* NewNode = new Node<T>(value);

            // 临时指针，用于遍历链表找到插入位置的前一个节点
            Node<T>* current = head;
            for(int i = 0; i < index - 1;i++) {
                current = current->next;
            }
            // 新节点的 next 指针指向当前节点的下一个节点
            NewNode->next = current->next;
            // 当前节点的 next 指针指向新节点
            current->next = NewNode;
            size++;
            return true;
        }

        // 遍历链表并对每个节点执行指定操作的函数模板
        template <typename Func>
        void traverse(Func func) {
            // 从链表头节点开始遍历
            Node<T>* current = head;
            while(current != nullptr) {
                // 对当前节点的数据执行传入的函数操作
                func(current->data);
                current = current->next;
            }
        }

        // 打印链表元素
        void print() const {
            Node<T>* current = head;
            while(current != nullptr) {
                std :: cout << current->data << " " << std :: endl;
                current = current->next;
            }
            //环行
            std :: cout << std :: endl;
        }
};

int main() {
    LinkedList<int> list;
    list.prepend(1);
    list.prepend(3);
    list.prepend(5);
    list.prepend(6);

    list.append(7);
    list.append(9);
    list.append(0);

    //遍历
    std::cout << "遍历链表: ";
    list.traverse([](int data ) {
        std :: cout << data << " " << std :: endl;
    });

    // 插入新节点
    list.insert(1, 10);
    std::cout << "插入新节点后: ";
    list.print();      
    return 0;
}